// #include <stdio.h>
// #include <stdlib.h>
// #include <stdbool.h>
// #include "windows.h"
//
// typedef int DataType;
//
// typedef struct TreeNode {
//     DataType value;
//     struct TreeNode* left;
//     struct TreeNode* right;
// } TreeNode;
//
// // 创建新节点
// TreeNode* CreateNode(DataType value) {
//     TreeNode* newNode = (TreeNode*)malloc(sizeof(TreeNode));
//     if (newNode == NULL) {
//         perror("Memory allocation failed");
//         exit(EXIT_FAILURE);
//     }
//     newNode->value = value;
//     newNode->left = newNode->right = NULL;
//     return newNode;
// }
//
// // 根据先序序列构建二叉树（递归辅助函数）
// // pre：先序序列数组
// // preIndex：当前处理的元素索引（指针传递以便修改）
// // low/high：当前子树在序列中的范围
// // size：序列总长度
// // 工作流程：
// // 1.创建当前根节点
// // 2.在序列中找到右子树起始点
// // 3.递归构建左子树和右子树
// TreeNode* BuildTreeFromPreorderHelper(DataType pre[], int* preIndex, int low, int high, int size) {
//     // 基线条件
//     if (*preIndex >= size || low > high) {
//         return NULL;
//     }
//
//     // 当前元素作为根节点
//     TreeNode* root = CreateNode(pre[*preIndex]);
//     (*preIndex)++;
//
//     // 如果只有一个元素，直接返回
//     if (low == high) {
//         return root;
//     }
//
//     // 找到第一个大于根节点值的元素，作为右子树的开始
//     int i;
//     for (i = low; i <= high; ++i) {
//         if (pre[i] > root->value) {
//             break;
//         }
//     }
//
//     // 递归构建左子树和右子树
//     root->left = BuildTreeFromPreorderHelper(pre, preIndex, *preIndex, i - 1, size);
//     root->right = BuildTreeFromPreorderHelper(pre, preIndex, i, high, size);
//
//     return root;
// }
//
// // 根据先序序列构建二叉搜索树
// // 调用BuildTreeFromPreorder函数构建树
// // 内部使用BuildTreeFromPreorderHelper递归构建
// TreeNode* BuildTreeFromPreorder(DataType pre[], int size) {
//     int preIndex = 0;
//     return BuildTreeFromPreorderHelper(pre, &preIndex, 0, size - 1, size);
// }
//
// // 后序遍历并将结果存入数组
// void PostOrderToArray(TreeNode* root, DataType arr[], int* index) {
//     if (root == NULL) {
//         return;
//     }
//     PostOrderToArray(root->left, arr, index);
//     PostOrderToArray(root->right, arr, index);
//     arr[(*index)++] = root->value;
// }
//
// // 先序遍历（用于验证）
// void PreOrder(TreeNode* root) {
//     if(root) {
//         printf("%d ",root->value);
//         PreOrder(root->left);
//         PreOrder(root->right);
//     }
// }
//
// // 后序遍历（打印）
// void PostOrder(TreeNode* root) {
//     if(root) {
//         PostOrder(root->left);
//         PostOrder(root->right);
//         printf("%d ",root->value);
//     }
// }
//
// // 释放内存
// void FreeTree(TreeNode* root) {
//     if (root) {
//         FreeTree(root->left);
//         FreeTree(root->right);
//         free(root);
//     }
// }
//
// int main() {
//     SetConsoleOutputCP(CP_UTF8);
//     // 先序序列
//     int Pre[] = {50, 30, 20, 40, 70, 60, 80};
//     int length = sizeof(Pre)/sizeof(Pre[0]);
//
//     // 按照先序序列生成二叉搜索树
//     TreeNode* root = BuildTreeFromPreorder(Pre, length);
//
//     printf("先序遍历结果（验证）: ");
//     PreOrder(root);
//     printf("\n");
//
//     // 后序遍历，结果保存到数组
//     DataType Post[length];
//     int index = 0;
//     PostOrderToArray(root, Post, &index);
//
//     printf("后序遍历结果: ");
//     for (int i = 0; i < length; i++) {
//         printf("%d ", Post[i]);
//     }
//     printf("\n");
//
//     // 也可以直接打印后序
//     printf("后序遍历验证: ");
//     PostOrder(root);
//     printf("\n");
//
//     FreeTree(root);
//     return 0;
// }